第4题
(共15分)
阅读下列说明和C代码，回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排好序的子数组得到排序结果。 下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下：
arr：待排序数组
p，q，r：一个子数组的位置为从p到q，另一个子数组的位置为从q+l到r
begin，end:待排序数组的起止位置
left，right:临时存放待合并的两个子数组
n1，n2:两个子数组的长度
i，j，k：循环变量
mid:临时变量
【问题：4.1】根据以上说明和C代码，填充C代码中的空(1)～(4)。
【问题：4.2】根据题干说明和以上c代码，算法采用了 (5) 算法设计策略。
分析时间复杂度时，列出其递归式为 (6) ，解得渐进时间复杂度为 (7) (用O符号表示)。空间复杂度为(8)(用O符号表示)。
分析时间复杂度时，列出其递归式为 (6) ，解得渐进时间复杂度为 (7) (用O符号表示)。空间复杂度为(8)(用O符号表示)。
【问题：4.3】两个长度分别为nl和n2的已排好序的子数组进行归并，根据上述C代码，则元素之间比较次数为 (9) 。